package SingleLinkedList;


class ListNode{
    public int val; //节点的数据域
    public ListNode next;// 节点的引用域

    public ListNode(int val) {
        this.val = val;
    }
}
public class MySingleLinkedList implements IList {
    public ListNode val;
    public ListNode next;
    public ListNode head;

    public void creatList(){
        ListNode listNode = new ListNode(12);
        ListNode listNode1 = new ListNode(23);
        ListNode listNode2 = new ListNode(34);
        ListNode listNode3 = new ListNode(56);
        ListNode listNode4 = new ListNode(67);
        ListNode listNode5 = new ListNode(78);
        ListNode listNode6 = new ListNode(89 );

        listNode.next = listNode1;
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;
        listNode5.next = listNode6;

        this.head = listNode;
    }

    @Override
    public int size() {
        ListNode cur = head;
        int len = 0;
        while(cur != null){
            len++;
            cur = cur.next;
        }
        return len;
    }
    /*
    头插法：直接赋值
     */
    @Override
    public void addFirst(int data) {
        ListNode node = new ListNode(data);
        node.next = head;
        head = node;
    }

    /*
    尾插法：1.先判断这个链表是不是空的（就是没有头）
    2.找到尾部的地址，再根据地址的引用来进行插入
     */
    @Override
    public void addLast(int data) {
        ListNode node = new ListNode(data);
        ListNode cur = head;
        if (head == null){
            head = node;
        }
        while(cur.next != null){
            cur = cur.next;
        }
        cur.next = node;
    }

    @Override
    public void addIndex(int index, int data) {
        try {
            //判断下标：
            checkIndex(index);
            //当插入位置为0:
            if (index == 0){
                addFirst(data);
                return;
            }
            //当插入位置为末尾:
            if (index == size()){
                addLast(data);
                return;
            }

            //中间位置的插入：
            ListNode node = new ListNode(data);
            ListNode cur = head;
            while(index - 1 != 0){//判断链表元素插入的位置
                cur = cur.next;
                index--;//当index自动-1，直到与条件成假时，证明要到了插入了的链表的位置
            }
        /*
        cur.next = node;
        node.next = cur.next;
        这么操作不可以，链表是根据引用来进行操作的，而不是去依靠其他的，所以先绑定了前链，而插入位置的后链会发生断链，由于是引用的丢失
         */
            node.next = cur.next;
            cur.next = node;
        }catch (IndexIlegal e){
            System.out.println("插入位置不合法");
            e.printStackTrace();
        }

    }

    private void checkIndex (int index) throws IndexIlegal {
        if (index < 0 || index > size()){
            throw new IndexIlegal("Index位置不合法");
        }
    }
    @Override
    public boolean contains(int key) {
        ListNode cur = head;
        while(cur != null){
            if(cur.val == key){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    /*@Override
    public void remove(int key) {
        if (head == null){
            return;
        }
        if (head.val == key){
            head = head.next;
            return;
        }
        //中间位置的删除：
        ListNode cur = head;
        while(cur != null){
            if (cur.next.val == key){
                ListNode del = cur.next;
                cur.next = del.next;
            }
            cur = cur.next;
        }
    }*/

    @Override
    public void remove(int key) {
        //判断链表为空
        if(head == null) {
            return;
        }
        //判断头节点
        if(head.val == key) {
            head = head.next;
            return;
        }
        //中间位置删除
        ListNode cur = findNodeOfKey(key);
        if(cur == null) {
            return;
        }
        ListNode del = cur.next;
        cur.next = del.next;
    }

    private ListNode findNodeOfKey(int key) {//查找key位置前一个元素cur
        ListNode cur = head;
        while (cur.next != null) {
            if(cur.next.val == key) {
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }

    @Override
    public void removeAllKey(int key) {//删除相同的所有的值
        //快慢指针技巧：
        ListNode cur = head.next;
        ListNode prev = head;
        if(head == null){
            return;
        }
        while(cur != null){
            if(cur.val == key){
                prev.next = cur.next;
                cur = cur.next;
            }else{
                prev = cur;
                cur = cur.next;
            }
        }
        if(head.val == key){
            head = head.next;
        }
    }

    @Override
    public void clear() {
        ListNode cur = head;//定义一个下标
        while(cur != null){
            ListNode curN = cur.next;
            //如果先修改置为空，那么不能链接引用了，
            //所以我们先定义一个值来进行保存起来，便于链接引用
            cur.next = null;
            cur = curN;
        }
        head = null;//所有的除了头节点的地址之外均置为空，然后我们手动对头节点来进行置空处理
    }

    @Override
    public void dispaly() {
        ListNode cur = head;
        while(cur != null){
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }
}